#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

bool isUnivalTree(struct TreeNode* root) {
    if (root == NULL)
    {
        return true;
    }
    if (root->left && root->left->val != root->val)
    {
        return false;
    }
    if (root->right && root->right->val != root->val)
    {
        return false;
    }
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

int maxDepth(struct TreeNode* root) {
    if (root == NULL)
    {
        return 0;
    }
    return (maxDepth(root->left) > maxDepth(root->right) ? maxDepth(root->left) : maxDepth(root->right)) + 1;
}

int TreeSize(struct TreeNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    return TreeSize(root->left) + TreeSize(root->right) + 1;
}

void PostOder(struct TreeNode* root, int* ret, int* i)
{
    if (root == NULL)
    {
        return;
    }
    PostOder(root->left, ret, i);
    PostOder(root->right, ret, i);
    ret[(*i)++] = root->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = TreeSize(root);
    int* ret = (int*)malloc(sizeof(int) * (*returnSize));
    int i = 0;
    PostOder(root, ret, &i);
    return ret;
}

void InOder(struct TreeNode* root, int* ret, int* i)
{
    if (root == NULL)
    {
        return;
    }
    InOder(root->left, ret, i);
    ret[(*i)++] = root->val;
    InOder(root->right, ret, i);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = TreeSize(root);
    int* ret = (int*)malloc(sizeof(int) * (*returnSize));
    int i = 0;
    InOder(root, ret, &i);
    return ret;
}

void PreOder(struct TreeNode* root, int* ret, int* i)
{
    if (root == NULL)
    {
        return;
    }
    ret[(*i)++] = root->val;
    PreOder(root->left, ret, i);
    PreOder(root->right, ret, i);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = TreeSize(root);
    int* ret = (int*)malloc(sizeof(int) * (*returnSize));
    int i = 0;
    PreOder(root, ret, &i);
    return ret;
}

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL)
    {
        return true;
    }
    if (p == NULL || q == NULL)
    {
        return false;
    }
    if (p->val != q->val)
    {
        return false;
    }
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if (root == NULL)
    {
        return false;
    }
    if (root->val == subRoot->val)
    {
        if (isSameTree(root, subRoot))
        {
            return true;
        }
    }
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

void rotate(struct TreeNode* root)
{
    if (root == NULL)
    {
        return;
    }
    struct TreeNode* p = root->left;
    root->left = root->right;
    root->right = p;
    rotate(root->left);
    rotate(root->right);
}

struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL)
    {
        return NULL;
    }
    rotate(root);
    return root;
}

bool symmetry(struct TreeNode* root, struct TreeNode* subroot)
{
    if (root == NULL && subroot == NULL)
    {
        return true;
    }
    if (root == NULL || subroot == NULL)
    {
        return false;
    }
    if (root->val != subroot->val)
    {
        return false;
    }
    return symmetry(root->left, subroot->right) && symmetry(root->right, subroot->left);
}

bool isSymmetric(struct TreeNode* root) {
    if (root == NULL)
    {
        return true;
    }
    return symmetry(root->left, root->right);
}